/*************************************************************************
	> File Name: 1673.找出最具竞争力的子序列.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 二  9/ 7 18:49:54 2021
 ************************************************************************/

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* mostCompetitive(int* nums, int numsSize, int k, int* returnSize){
    *returnSize = k;
    if (numsSize == 0) return NULL;

    int n = numsSize;
    int sta[n], top = 0;
    int *ret = (int *)malloc(sizeof(int) * k);
    
    int removeCount = n - k;
    for (int i = 0; i < n; i++) {
        while (removeCount > 0 && top && nums[i] < nums[sta[top - 1]]) {
            removeCount--;
            top--;
        }
        sta[top++] = i;
    }
    //此时单调栈中保存的数组下标对应的数据从栈底到栈顶是单调递增的
    //从栈底开始的k个元素就是最终的答案
    while (removeCount--) {
        --top;
    }
    
    int ind = k - 1;
    while (ind >= 0 && top) {
        ret[ind--] = nums[sta[top - 1]];
        top--;
    }

    return ret;
}
